﻿#define _CRT_SECURE_NO_WARNINGS 1


//如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
//每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/isomorphic-strings
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//#include<stdio.h>
//#include<stdlib.h>
//#include<Stdbool.h>
//
//bool isIsomorphic(char* s, char* t) {
//	int ss[128] = { 0 };
//	int tt[128] = { 0 };
//	int sc = 0, tc = 0;
//	for (int i = 0; s[i] != '\0'; i++) {
//		if (ss[s[i]] == 0) ss[s[i]] = ++sc;
//		if (tt[t[i]] == 0) tt[t[i]] = ++tc;
//		if (ss[s[i]] != tt[t[i]]) return false;
//	}
//	return true;
//}
//
//int main()
//{
//	char arr1[] = "abbc";
//	char arr2[] = "cddf";
//	if (isIsomorphic(arr1, arr2))
//	{
//		printf("是\n");
//	}
//	else
//	{
//		printf("否\n");
//	}
//	system("pause");
//	return 0;
//}



//389. 找不同
//给定两个字符串 s 和 t ，它们只包含小写字母。
//
//字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
//
//请找出在 t 中被添加的字母。
//#include<stdio.h>
//#include<stdlib.h>
//#include<string.h>
//int cmp_char(const void* e1, const void* e2)
//{
//    return strcmp ( (char*)e1,(char*)e2);
//}
//
//char findTheDifference(char* s, char* t) {
//    int len = strlen(s);
//    if (len == 0)
//        return t[0];
//
//    qsort(s, len, sizeof(s[0]), cmp_char);
//    qsort(t, strlen(t), sizeof(t[0]), cmp_char);
//    int i = 0;
//    while (*t != '\0')
//    {
//        if (s[i] == t[i])
//        {
//            i++;
//        }
//        else
//        {
//            return t[i];
//        }
//    }
//    return t[i];
//}


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//计算法
//char findTheDifference(char* s, char* t) {
//    char cur[26];
//    memset(cur, 0, sizeof(cur));
//    int len1 = strlen(s);
//    int len2 = strlen(t);
//    int i = 0;
//    for (i = 0; i < len1; i++)
//    {
//        cur[s[i] - 'a'] += 1;
//    }
//    for (i = 0; i < len2; i++)
//    {
//        cur[t[i] - 'a']--;
//        if (cur[t[i] - 'a'] < 0)
//        {
//            return t[i];
//        }
//    }
//    return t[i];
//}

//位运算
//char findTheDifference(char* s, char* t) {
//    //位运算
//    int ret = 0;
//    int len1 = strlen(s), len2 = strlen(t);
//    int i = 0;
//    for (i = 0; i < len1; i++)
//    {
//        ret ^= s[i];
//    }
//    for (i = 0; i < len2; i++)
//    {
//        ret ^= t[i];
//    }
//    return ret;
//}
//int main()
//{
//    char s[] = "abcd";
//    char t[] = "abcde";
//    printf("%c\n", findTheDifference(s, t));
//    system("pause");
//}
//void print(int** a, int N, int M)
//{
//    int i = 0;
//    int j = 0;
//    for (i = 0; i < N; i++)
//    {
//        for (j = 0; j < M; j++)
//        {
//            printf("%d ", a[i][j]);
//        }
//        printf("\n");
//    }
//}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Postion
{
    int row;
    int col;
}PT;

#pragma once
#include<assert.h>

typedef PT STDataType;
// 支持动态增长的栈
struct Stack
{
    STDataType* a;
    int top; //栈顶
    int capacity;  //栈的容量
};

typedef struct Stack ST;

ST q1;
//初始化栈
void STinit(ST* ps);

//入栈
void STPush(ST* ps, STDataType x);

//出栈
void StackPop(ST* ps);

// 获取栈顶元素
STDataType StackTop(ST* ps);

// 获取栈中有效元素个数
int STSize(ST* ps);


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* ps);


// 销毁栈
void STDestroy(ST* ps);

//初始化栈
void STinit(ST* ps)
{
    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->a == NULL)
    {
        perror("err:");
    }
    else
    {
        //栈顶先从0开始
        ps->top = 0;
        ps->capacity = 4;
    }
}

//入栈
void STPush(ST* ps, STDataType x)
{
    assert(ps);
    //是否需要增容
    if (ps->top == ps->capacity)
    {
        STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("err");
        }
        else
        {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }
    ps->a[ps->top] = x;
    ps->top++;
}

//出栈
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

//获得栈顶元素
STDataType StackTop(ST* ps)
{
    assert(ps);
    return ps->a[ps->top - 1];
}


int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int STEmpty(ST* ps)
{
    assert(ps);
    /*if (ps->top == 0)
        return -1;
    else
        return 0;*/
    return ps->top == 0;
}

// 销毁栈
void STDestroy(ST* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

void PirntPath(ST* qs)
{
    ST q2;
    STinit(&q2);
    while (!STEmpty(&q1))
    {
        STPush(&q2, StackTop(&q1));
        StackPop(&q1);
    }

    while (!STEmpty(&q2))
    {
        PT Q = StackTop(&q2);
        printf("(%d,%d)\n", Q.col, Q.row);
        StackPop(&q2);
    }
    
}
bool IsPass(int** maze, int N, int M, PT cur)
{
    if (cur.col >= 0 && cur.col < N
        && cur.row >= 0 && cur.row < M
        && maze[cur.col][cur.row] == 0)
    {
        return true;
    }
    return false;
}

bool GetMazePath(int** maze, int N, int M, PT cur)
{
    STPush(&q1, cur);
    //找到出口
    if (cur.col == N - 1 && cur.row == M - 1)
        return true;
    PT next = { 0 };
    maze[cur.col][cur.row] = 2;
    
    
    //上
    next = cur;
    next.col -= 1;
    if (IsPass(maze, N, M, next)) //判断是否有位置走
    {
        if(GetMazePath(maze, N, M, next))
           return true;
    }

    //下
    next = cur;
    next.col += 1;
    if (IsPass(maze, N, M, next))
    {
        if (GetMazePath(maze, N, M, next))
           return true;
    }

    //左
    next = cur;
    next.row -= 1;
    if (IsPass(maze, N, M, next))
    {
        if (GetMazePath(maze, N, M, next));
          return true;
    }

    //右
    next = cur;
    next.row += 1;
    if (IsPass(maze, N, M, next))
    {
        if (GetMazePath(maze, N, M, next))
         return true;
    }
    StackPop(&q1);
    return false;
}


int main() {
    int N, M;
    scanf("%d%d", &N, &M);

    //动态开辟二维数组
    int** maze = (int**)malloc(sizeof(int*) * N);
    int i = 0;
    for (i = 0; i < N; i++)
    {
        maze[i] = (int*)malloc(sizeof(int) * M);
    }
    for (i = 0; i < N; i++)
    {
        int j = 0;
        for (j = 0; j < M; j++)
        {
            //二维数组输入
            scanf("%d", &maze[i][j]);
        }
    }

    //二维数组打印
    //print(maze, N, M);
    STinit(&q1);
    PT errey = { 0,0 };
    //迷宫
    if (GetMazePath(maze, N, M, errey))
    {
        PirntPath(&q1);
    }
    else
    {
        printf("迷宫没路\n");
    }
    system("pause");
    return 0;
}